Short text classification in twitter to improve information filtering.
In microblogging services such as Twitter, the users may become overwhelmed by the raw data. One solution to this problem is the classification of short text messages. As short texts do not provide sufficient word occurrences, traditional classification methods such as “Bag-Of-Words ” have limitations. To address this problem, we propose to use a small set of domain-specific features extracted from the author’s profile and text. The proposed approach effectively classifies the text to a predefined set of generic classes
Mutual Information Based Extrinsic Similarity for Microarray Analysis.

Secondary bitmap indexes with vertical and horizontal partitioning.

Bitmap%2Dbased Index Structures.

MicroarrayDesigner an online search tool and repository for near%2Doptimal microarray experimental designs.

Distance%2Dbased indexing of residue contacts for protein structure retrieval and alignment.

Distance%2Dbased indexing of residue contacts for protein structure retrieval and alignment.

Automated Data Discovery in Similarity Score Queries.
Abstract. A vast amount of information is being stored in scientific databases on the web. The dynamic nature of the scientific data, the cost of providing an up-to-date snapshot of the whole database, and proprietary considerations compel the database owners to hide the original data behind search interfaces. The information is often provided to researchers through similarity-search query interfaces, which limits a proper and focused analysis of the data. In this study, we present systematic methods of data discovery through similarity-score queries in such “uncooperative ” databases. The methods are generalized to multidimensional data, and to L-p norm distance functions. The accuracy and performance of our methods are demonstrated on synthetic and real-life datasets. The methods developed in this study enable the scientists to obtain the data within the range of their research interests, overcoming the limitations of the similarity-search interface. The results of this study also present implications in data privacy and security areas, where the discovery of the original data is not desired. 1
Analysis of Basic Data Reordering Techniques.
Abstract. Data reordering techniques are applied to improve the space and time efficiency of storage and query systems in various scientific and commercial applications. Run-length encoding is a prominent approach of compression in many areas, whose performance is significantly enhanced by achieving longer and fewer “runs ” through data reordering. In this paper we theoretically study two reordering techniques, namely lexicographical order and Gray code order. We analyze these two methods in the context of bitmap indexes, which are known to have high query performances. We take into account the two commonly used bitmap encodings: equality and range. Our analysis indicates that, when we have all the possible data tuples, both ordering methods perform the same with equality encoding. However, Gray code achieves better compression with range encoding. Experimental results are provided to validate the theoretical analysis. 1
Indexing%2C High Dimensional.
This paper addresses the problem of quickly performing point queries against high-dimensional regions. Such queries are useful in the increasingly important problems of multimedia identification and retrieval, where different database entries have different metrics for similarity. While the database literature has focused on indexing for high-dimensional nearest neighbor and epsilon range queries, indexing for point queries against high-dimensional regions has not been addressed. We present an efficient indexing method for these queries, which relies on the combination of redundancy and bit vector indexing to achieve significant performance gains. We have implemented our approach in a real-world audio fingerprinting system, and have obtained a factor of 56 speed-up over linear scan. Furthermore, the well-known Hilbert bulk-loaded R-Trees, a technique capable of searching low-dimensional regions, are shown to be ineffective in our audio fingerprinting system, because of the inherently high-dimensional properties of the problem. 1
An enhanced partial order curve comparison algorithm and its application to analyzing protein folding trajectories.

CellTrack an open%2Dsource software for cell tracking and motility analysis.

Integrated search and alignment of protein structures.
Motivation: Identification and comparison of similar threedimensional (3D) protein structures has become an even greater challenge in the face of the rapidly growing structure databases. Here, we introduce Vorometric, a new method that provides efficient search and alignment of a query protein against a database of protein structures. Voronoi contacts of the protein residues are enriched with the secondary structure information and a metric substitution matrix is developed to allow efficient indexing. The contact hits obtained from a distance-based indexing method are extended to obtain highscoring segment pairs, which are then used to generate structural alignments. Results: Vorometric is the first to address both search and alignment problems in the protein structure databases. The experimental results show that Vorometric is simultaneously effective in retrieving similar protein structures, producing high-quality structure alignments, and identifying cross-fold similarities. Vorometric outperforms current structure retrieval methods in search accuracy, while requiring comparable running times. Furthermore, the structural superpositions produced are shown to have better quality and coverage, when compared with those of the popular structure alignment tools. Availability: Vorometric is available as a web service at
Incremental Maintenance of Online Summaries Over Multiple Streams.

Online Index Recommendations for High%2DDimensional Databases Using Query Workloads.%
We consider the problem of parallelizing highdimensional proximity joins. We present a parallel multidimensional join algorithm based on an the epsilon-kdB tree and compare it with the more common approach of space partitioning. An evaluation of the algorithms on an IBM SP2 shared-nothing multiprocessor is presented using both synthetic and real-life datasets. We also examine the effectiveness of the algorithms in the context of a specific data-mining problem, that of finding similar time-series. The empirical results show that our algorithm exhibits good performance and scalability, as well an ability to handle dataskew.   1 Introduction  Many emerging applications require efficient processing of proximity joins on high-dimensional points[20]. Typical queries in these applications include:  ffl Find all pairs of similar images (often as a prelude to clustering the images).  ffl Retrieve music scores similar to a target music score.  ffl Discover all stocks with similar price movements...
Online Index Recommendations for High%2DDimensional Databases Using Query Workloads.%
We consider the problem of parallelizing highdimensional proximity joins. We present a parallel multidimensional join algorithm based on an the epsilon-kdB tree and compare it with the more common approach of space partitioning. An evaluation of the algorithms on an IBM SP2 shared-nothing multiprocessor is presented using both synthetic and real-life datasets. We also examine the effectiveness of the algorithms in the context of a specific data-mining problem, that of finding similar time-series. The empirical results show that our algorithm exhibits good performance and scalability, as well an ability to handle dataskew.   1 Introduction  Many emerging applications require efficient processing of proximity joins on high-dimensional points[20]. Typical queries in these applications include:  ffl Find all pairs of similar images (often as a prelude to clustering the images).  ffl Retrieve music scores similar to a target music score.  ffl Discover all stocks with similar price movements...
A Multi%2Dmetric Similarity Based Analysis of Microarray Data.

Incremental Quantization for Aging Data Streams.

Update Conscious Bitmap Indices.
Bitmap indices have been widely used in several domains such as data warehousing and scientific applications due to their efficiency in answering certain query types over large data sets. However, their utilization has been largely limited to read-only data sets or to static snapshots of data due to the cost associated with the update and append of new data. Typically, several bitmaps are associated with each indexed attribute in a table, i.e. one for each attribute value, bin, or range. Each one of these bitmaps needs to be updated to reflect a new, appended row. Since a given table could be represented by hundreds or even thousands of bitmaps, the insertion of a single record can be prohibitively costly. In order to transfer the fast query response times offered by bitmap indices to dynamic database domains, we propose an update conscious bitmap index that provides a mechanism to quickly update bitmaps to reflect dynamic database changes. For an insert operation only the bitmaps that represent the values being inserted need to be updated. We formalize the insert and delete operations of the proposed technique and provide a cost model for bitmap updates. We compare the update conscious bitmaps to traditional bitmaps in terms of storage space, update performance, and query execution time. 1
A General Framework for Modeling and Processing Optimization Queries.

LFM%2DPro a tool for detecting significant local structural sites in proteins.

Data space mapping for efficient I%2FO in large multi%2Ddimensional databases.

Indexing Incomplete Databases.

Indexing Incomplete Databases.

A Vision for Cyberinfrastructure for Coastal Forecasting and Change Analysis.

Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps.
Bitmap indices have been widely and successfully used in scientific and commercial databases. Compression techniques based on run-length encoding are used to improve the storage performance. However, these techniques introduce significant overheads in query processing even when only a few rows are queried. We propose a new bitmap encoding scheme based on multiple hashing, where the bitmap is kept in a compressed form, and can be directly accessed without decompression. Any subset of rows and/or columns can be retrieved efficiently by reconstructing and processing only the necessary subset of the bitmap. The proposed scheme provides approximate results with a trade-off between the amount of space and the accuracy. False misses are guaranteed not to occur, and the false positive rate can be estimated and controlled. We show that query execution is significantly faster than WAH-compressed bitmaps, which have been previously shown to achieve the fastest query response times. The proposed scheme achieves accurate results (90 %-100%) and improves the speed of query processing from 1 to 3 orders of magnitude compared to WAH. 1.
Efficient parallel processing of range queries through replicated declustering.
A common technique used to minimize I/O in data intensive applications is data declustering over parallel servers. This technique involves distributing data among several disks so as to parallelize query retrieval and thus, improve performance. We focus on optimizing access to large spatial data, and the most common type of queries on such data, i.e., range queries. An optimal declustering scheme is one in which the processing for all range queries is balanced uniformly among the available disks. It has been shown that single copy based declustering schemes are non-optimal for range queries. In this paper, we integrate replication in conjunction with parallel disk declustering for efficient processing of range queries. We note that replication is largely used in database applications for several purposes like load balancing, fault tolerance and availability of data. We propose theoretical foundations for replicated declustering and propose a class of replicated declustering schemes, periodic allocations, which are shown to be strictly optimal for a number of disks. We propose a framework for replicated declustering, using a limited amount of replication and provide extensions to apply it on real data, which include arbitrary grids and a large number of disks. Our framework also provides an effective indexing scheme that enables fast identification of data of interest in parallel servers. In addition to optimal processing of single queries, we show that this framework is effective for parallel processing of multiple queries. We present experimental results comparing the proposed replication scheme to other techniques for both single queries and multiple queries, on synthetic and real data sets.
Access Structures for Angular Similarity Queries.

Information Mining Over Heterogeneous and High%2DDimensional Time%2DSeries Data in Clinical Trials Databases.

High dimensional nearest neighbor searching.
Searching for nearest neighbors among a large number of vectors in a high dimensional space is usually costly and time-consuming. To support such high dimensional nearest neighbor searches, low dimensional approximations of vectors are usually used to filter out many vectors (and hence to reduce the search space). However, most existing studies use only a single level approximations. This paper, instead, proposes a multilevel approximation scheme. For each data vector, with its approximation (at any given level), both a lower bound and an upper bound can be derived on its distance from the query vector. Distance bounds derived at a finer approximation level are tighter, but the cost to derive them is higher. The paper then presents two multilevel filtering methods using this approximation scheme. The coarsest level approximations, which are low in both volume and dimensionality, are indexed in a R-tree, and are used first to compute a set of candidate vectors. Finer level approximations ar...
Online summarization of dynamic time series data.

Compressing Bitmap Indices by Data Reorganization.
Many scientific applications generate massive volumes of data through observations or computer simulations, bringing up the need for effective indexing methods for efficient storage and retrieval of scientific data. Unlike conventional databases, scientific data is mostly read-only and its volume can reach to the order of petabytes, making a compact index structure vital. Bitmap indexing has been successfully applied to scientific databases by exploiting the fact that scientific data are enumerated or numerical. Bitmap indices can be compressed with variants of run length encoding for a compact index structure. However even this may not be enough for the enormous data generated in some applications such as high energy physics. In this paper, we study how to reorganize bitmap tables for improved compression rates. Our algorithms are used just as a preprocessing step, thus there is no need to revise the current indexing techniques and the query processing algorithms. We introduce the tuple reordering problem, which aims to reorganize database tuples for optimal compression rates. We propose Gray code ordering algorithm for this NP-Complete problem, which is an inplace algorithm, and runs in linear time in the order of the size of the database. We also discuss how the tuple reordering problem can be reduced to the traveling salesperson problem. Our experimental results on real data sets show that the compression ratio can be
Optimal Data%2DSpace Partitioning of Spatial Data for Parallel I%2FO.
It is desirable to design partitioning methods that minimize the I/O time incurred during query execution in spatial databases. This paper explores optimal partitioning for two-dimensional data for a class of queries and develops multi-disk allocation techniques that maximize the degree of I/O parallelism obtained in each case. We show that hexagonal partitioning has optimal I/O performance for circular queries among all partitioning methods that use convex non-overlapping regions. An analysis and extension of this result to all possible partitioning techniques is also given. For rectangular queries, we show that hexagonal partitioning has overall better I/O performance for a general class of range queries, except for rectilinear queries, in which case rectangular grid partitioning is superior. By using current algorithms for rectangular grid partitioning, parallel storage and retrieval algorithms for hexagonal partitioning can be constructed. Some of these results carry over to circular partitioning of the data—which is an example of a non-convex region.
Vector Space Indexing for Biosequence Similarity Searches.

A Time Series Analysis of Microarray Data.

Replicated Declustering of Spatial Data.
The problem of disk declustering is to distribute data among multiple disks to reduce query response times through parallel I/O. A strictly optimal declustering technique is one that achieves optimal parallel I/O for all possible queries. In this paper, we focus on techniques that are optimized for spatial range queries. Current declustering techniques, which have single copies of the data, have been shown to be suboptimal for range queries. The lower bound on extra disk accesses is proved to  N) for N disks even in the restricted case of an N-by-N grid, and all current approaches have been trying to achieve this bound. Replication is a well-known and effective solution for several problems in databases, especially for availability and load balancing. In this paper, we explore the idea of replication in the context of declustering and propose a framework where strictly optimal parallel I/O is achievable using a small amount of replication. We provide some theoretical foundations for replicated declustering, e.g., a bound for number of copies for strict optimality on any number of disks, and propose a class of replicated declustering schemes, periodic allocations, which are shown to be strictly optimal. The results for optimal disk allocation are extended for larger number of disks by increasing replication. Our techniques and results are valid for any arbitrary a-by-b grids, and any declustering scheme can be further improved using our replication framework. Using the framework, we perform experiments to identify a strictly optimal disk access schedule for any given arbitrary range query. In addition to the theoretical bounds, we compare the proposed replication based scheme to other existing techniques by performing experiments on real datasets.
Dimensionality Reduction and Similarity Computation by Inner%2DProduct Approximations.
We develop dynamic dimensionality reduction based on the approximation of the standard inner-product. The innerproduct, by itself, is used as a distance measure in a wide area of applications such as document databases, e.g. latent semantic indexing (LSI). A first order approximation to the inner-product is usually obtained from the Cauchy-Schwarz inequality. The method proposed in this paper refines such an approximation by using higher order power symmetric functions of the components of the vectors, which are powers of the p-norms of the vectors for p = 1; 2; : : : ; m. We show how to compute fixed coefficients that work as universal weights based on the moments of the probability density function assumed for the distribution of the components of the input vectors in the data set. Our experiments on synthetic and document data show that with this technique, the similarity between two objects in high dimensional space for certain applications can be accurately approximated by a signi...
Effective Indexing and Filtering for Similarity Search in Large Biosequence Databases.
We present a multi-dimensional indexing approach for fast sequence similarity search in DNA and protein databases. In particular, we propose effective transformations of subsequences into numerical vector domains and build efficient index structures on the transformed vectors. We then define distance functions in the transformed domain and examine properties of these functions. We experimentally compared their (a) approximation quality for k-Nearest Neighbor (k-NN) queries, (b) pruning ability and (c) approximation quality for e-range queries. Results for k-NN queries, which we present here, show that our proposed distances FD2 and WD2 (i.e. Frequency and Wavelet Distance functions for 2-grams) perform significantly better than the others&#039;. We then develop effective index structures, based on R-trees and scalar quantization, on top of transformed vectors&#039; and distance functions. Promising results from the experiments on real biosequence data sets are presented.
High dimensional reverse nearest neighbor queries.
Reverse Nearest Neighbor (RNN) queries are of particular interest in a wide range of applications such as decision support systems, profile based marketing, data streaming, document databases, and bioinformatics. The earlier approaches to solve this problem mostly deal with two dimensional data. However most of the above applications inherently involve high dimensions and high dimensional RNN problem is still unexplored. In this paper, we propose an approximate solution to answer RNN queries in high dimensions. Our approach k-NN and RNN. It works in two phases. In the first phase the k-NN of a query point is found and in the next phase they are further analyzed using a novel type of query Boolean Range Query (BRQ). Experimental results show that BRQ is much more e#cient than both NN and range queries, and can be e#ectively used to answer RNN queries. Performance is further improved by running multiple BRQ simultaneously. The proposed approach can also be used to answer other variants of RNN queries such as RNN of order k, bichromatic RNN, and Matching Query which has many applications of its own. Our technique can e#ciently answer NN, RNN, and its variants with approximately same number of I/O as running a NN query.
Dimensionality reduction using magnitude and shape approximations.
High dimensional data sets are encountered in many modern database applications. The usual approach is to construct a summary of the data set through a lossy compression technique, and use this lower dimensional synopsis to provide fast, approximate answers to the queries. In this paper, we develop a novel dimensionality reduction technique based on partitioning the high dimensional vector space into orthogonal subspaces. First, we find a relation between the Euclidian distance of two n-dimensional vectors and the Euclidian distances of their projections on the orthogonal subspaces. Then, based on this relation we develop a method to approximate the Euclidian distance using novel inner product approximation. This process allows us to incorporate the shape information of the vectors to this approximation. While the inner product approximation is symmetric, i.e., captures only the magnitude information of the data, the proposed method takes both the magnitude and shape information of the original vectors into account through partitioning. In the experiments, we demonstrate the effectiveness of our technique by comparing it with commonly used methods.
CoMRI A Compressed Multi%2DResolution Index Structure for Sequence Similarity Queries.
In this paper, we present CoMRI, Compressed MultiResolution  Index, our system for fast sequence similarity search in DNA sequence databases. We employ Virtual Bounding Rectangle (VBR) concept to build a compressed, grid style index structure. An advantage of grid format over trees is subsequence location information is given by the order of corresponding VBR in the VBR list. Taking advantage of VBRs, our index structure fits into a reasonable size of memory easily. Together with a new optimized multiresolution search algorithm, the query speed is improved significantly. Extensive performance evaluations on Human Chromosome sequence data show that VBRs save 80%-93% index storage size compared to MBRs (Minimum ounding Rectangles) and new search algorithm prunes almost all unnecessary VBRs which guarantees efficient disk I/O and CPU cost. According to the results of our experiments, the performance of CoMRI is at least 100 times faster than MRS which is another grid index structure introduced very recently. 1 
Peer%2Dto%2DPeer Spatial Queries in Sensor Networks.
Sensor networks, that consist of potentially several thousands of nodes each with sensing (heat, sound, light, magnetism, etc.) and wireless communication capabilities, provide great opportunities for monitoring spatial information about a region of interest. Although spatial query execution has been studied extensively in the context of database systems (e.g., indexing technologies), these solutions are not directly applicable in the context of sensor networks due to the decentralized nature of the sensor networks and the limited computational power and energy scarcity of individual sensor nodes. In this paper,
Efficient k%2DNN Search on Streaming Data Series.
Data streams are common in many recent applications, e.g. stock quotes, e-commerce data...
VQ%2Dindex an index structure for similarity searching in multimedia databases.
In this paper, we introduce a novel indexing technique based on efficient compression of the feature space for approximate similarity searching in large multimedia databases. Its main novelty is that state-of-the-art tools from the discipline of data compression are adopted to optimize the complexity-performance tradeoff in large data sets. The design procedure optimizes the query access time by jointly accounting for both database distribution and query statistics. We achieve efficient compression by using appropriate vector quantization (VQ) techniques, namely, multi-stage VQ and split-VQ, which are especially suited for limited memory applications. We partition the data set using the accumulated query history, and each partition of data points is separately compressed using a vector quantizer tailored to its distribution. The employed VQ techniques inherently provide a spectrum of points to choose from on the time/accuracy plane. This property is especially crucial for large multimedia databases where I/O time is a bottleneck, because it offers the flexibility to trade time for better accuracy. Our experiments demonstrate speedups of 20 to 35 over a VA-file technique that has been adapted for approximate nearest neighbor searching.
Vulnerabilities in similarity search based systems.
Similarity based queries are common in several modern database  applications, such as multimedia, scientific, and biomedical databases. In most of these systems, database responds with the tuple with the closest match according to some metric. In this paper we investigate some important security issues related to similarity search in databases. We investigate the vulnerability of such systems against users who try to copy the database by sending automated queries. We analyze two models for similarity search, namely reply model and score model. Reply model responds with the tuple with best match and score model responds with only the score of similarity search. For these models we analyze possible ways of attacks and strategies that can be used to detect attacks. Our analysis shows that in score model it is much easier to plug the vulnerabilities than in reply model. Sophisticated attacks can easily be used in reply model and the database is limited in capability to prevent such attacks.
Optimal Parallel I%2FO Using Replication.
There has been a lot of interest in declustering spatial data for efficient parallel I/O. Declustering is used to distribute blocks of data among multiple devices, thus enabling parallel I/O access and reducing query response times. A strictly optimal declustering, or disk allocation, technique is the one that achieves optimal performance for all possible queries. It has been proved that it is impossible to reach strict optimality for parallel I/O in general scenarios, and the lower bound on extra disk accesses is proved to be 1 6 m) for m disks even in the restricted case of m-by-m grid. Therefore, all current approaches have been trying to achieve this bound. In this paper, we propose to use replication to reach optimal parallel I/O in multi-disk/processor architectures. Replication is a well-known and effective solution for several problems in a database context, especially for availability and load balancing problems. We explore the idea of replication in the context of declustering and propose optimal declustering techniques using intelligent replication. We investigate whether strictly optimal parallel I/O is achievable using a small amount of replication. We especially focus on allocations based on latin squares and derive several nice properties for replication and declustering purposes. Three different replication strategies are proposed and evaluated. Using the proposed schemes, strict optimality is reached, even with a single replication, for all possible range queries and for several number of disks. We first show this for m-by-m grid on m disks, and then generalize it to any arbitrary a-by-b grids. We also show how to efficiently find optimal disk accesses for a given arbitrary query by storing minimal information.
Efficient Processing of Conical Queries.
Conical queries are a novel type of query with an increasing number of applications. Traditional index structures and retrieval mechanisms, in general, have been optimized for rectangular and circular queries, rather than conical queries. In this paper, we focus on conical queries which can be  defined as a multi-dimensional cone in a multi-dimensional data space. We develop a model for expressing such queries and suggest efficient techniques for evaluating them. In particular, we explore  the retrieval problem in the context of conical query processing and develop multi-disk allocation methods specifically for processing conical queries.  
Optimal Partitioning for Efficient I%2FO in Spatial Databases.
It is desirable to design partitioning techniques that minimize the I/O time incurred during query  execution in spatial databases. In this paper, we explore optimal partitioning techniques for spatial  data for different types of queries, and develop multi-disk allocation techniques that maximize the degree  of I/O parallelism obtained during the retrieval. We show that hexagonal partitioning has optimal  I/O cost for circular queries compared to all possible non-overlapping partitioning techniques that use  convex regions. For rectangular queries, we show that although for the special case when queries are  rectilinear, rectangular grid partitioning gives superior performance, hexagonal partitioning has overall  better I/O cost for a general class of range queries. We then discuss parallel storage and retrieval  techniques for hexagonal partitioning using current techniques for rectangular grid partitioning.
Approximate Nearest Neighbor Searching in Multimedia Databases.
In this paper, we develop a general framework for approximate nearest neighbor queries. We categorize the current approaches for nearest neighbor query processing based on either their ability to reduce the data set that needs to be examined, or their ability to reduce the representation size of each data object. We first propose modifications to wellknown techniques to support the progressive processing of approximate nearest neighbor queries. A user may therefore stop the retrieval process once enough information has been returned. We then develop a new technique based on clustering that merges the benefits of the two general classes of approaches. Our cluster-based approach allows a user to progressively explore the approximate results with increasing accuracy. We propose a new metric for evaluation of approximate nearest neighbor searching techniques. Using both the proposed and the traditional metrics, we analyze and compare several techniques with a detailed performance evaluation. We demonstrate the feasibility and efficiency of approximate nearest neighbor searching. We perform experiments on several real data sets and establish the superiority of the proposed cluster-based technique over the existing techniques for approximate nearest neighbor searching. 1
Constrained Nearest Neighbor Queries.

Vector Approximation based Indexing for Non%2Duniform High Dimensional Data Sets.
With the proliferation of multimedia data, there is increasing need to support the indexing and searching of high dimensional data. Recently, a vector approximation based technique called VA-file has been proposed for indexing high dimensional data. It has been shown that the VA-file is an effective technique compared to the current approaches based on space and data partitioning. The VA-file gives good performance especially when the data set is uniformly distributed. Real data sets are not uniformly distributed, are often clustered, and the dimensions of the feature vectors in real data sets are usually correlated. More careful analysis for nonuniform or correlated data is needed for effectively indexing high dimensional data. We propose a solution to these problems and propose the VA+-file, a new technique for indexing high dimensional data sets based on vector approximations. We conclude with an evaluation of nearest neighbor queries and show that the VA+-file technique res...
Dimensionality Reduction and Similarity Computation by Inner Product Approximations.
We develop dynamic dimensionality reduction based on the approximation of the standard inner-product. The innerproduct, by itself, is used as a distance measure in a wide area of applications such as document databases, e.g. latent semantic indexing (LSI). A first order approximation to the inner-product is usually obtained from the Cauchy-Schwarz inequality. The method proposed in this paper refines such an approximation by using higher order power symmetric functions of the components of the vectors, which are powers of the p-norms of the vectors for p = 1; 2; : : : ; m. We show how to compute fixed coefficients that work as universal weights based on the moments of the probability density function assumed for the distribution of the components of the input vectors in the data set. Our experiments on synthetic and document data show that with this technique, the similarity between two objects in high dimensional space for certain applications can be accurately approximated by a signi...
Clustering Declustered Data for Efficient Retrieval.
Modern databases increasingly integrate new kinds of information, such as multimedia information in the form of image, video, and audio data. Both the dimensionality and the amount of data that need to be processed is increasing rapidly, increasing the demand for the ecient retrieval of large amounts of multi-dimensional data. Declustering techniques for multi-disk architectures have been effectively used for storage. In this paper, we first establish that besides exploiting the parallelism, a careful organization of each disk must be considered for fast searching. We introduce the notion of page allocation and data space mapping which can be used to organize and retrieve multidimensional data. We develop these notions based on three di erent partitioning strategies: regular grid partitioning, concentric hypercubes and hyperpyramids. We develop techniques that satisfy efficient retrieval by optimizing the number of buckets retrieved by the query, disk arm movement and I/O parallelism. We ...
Concentric Hyperspaces and Disk Allocation for Fast Parallel Range Searching.
Data partitioning and declustering have been extensively used in the past to parallelize I/O for range queries. Numerous declustering and disk allocation techniques have been proposed in the literature. However, most of these techniques were primarily designed for two-dimensional data and for balanced partitioning of the data space. As databases increasingly integrate multimedia information in the form of image, video, and audio data, it is necessary to extend the declustering techniques for multidimensional data. In this paper, we first establish that traditional declustering techniques do not scale for high-dimensional data. We then propose several new partitioning schemes based on concentric hyperspaces. We then develop disk allocation methods for each of the proposed schemes. We conclude with an evaluation of range queries based on these schemes and show that partitioning based on concentric hyperspaces has a significant advantage over balanced partitioning approach for parallel I/O. 1
